
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=70,M=59;
const ll P=1e9+7,MX=1e18;
ll t,a,b,c,ans,sja[N],sjb[N],sj[N],f[N],cp[N][N];
ll gcd (ll a,ll b) {return (b==0?a:gcd(b,a%b));}
ll qpow (ll a,ll b) {
	ll res=1;
	while (b) {
		if (b&1) {
			if (res>MX/a) {return MX+1;}
			res*=a;
			if(b==1)break;
		}
		if (a>MX/a) {return MX+1;}
		a*=a,b>>=1;
	}
	return res;
}
ll gt (ll a,ll b) {
	ll l=1,r=sj[b];
	while (l<r) {
		ll mid=(l+r+1)>>1;
		if (qpow(mid,b)<=a) {l=mid;}
		else {r=mid-1;}
	}
	return l;
}
ll calc (ll x) {
	ll res=1,cpx=x;
	for (int i=2;i<=x;i++) {
		if (x%i==0) {
			ll cnt=0;
			while (x%i==0) {cnt++,x/=i;}
			cnt=(cnt+cpx-1)/cpx;
			for (int j=1;j<=cnt;j++) {res*=i;}
		}
	}
	return res;
}
int main () {
	freopen("alien.in","r",stdin);
	freopen("alien.out","w",stdout);
	for (int i=1;i<=M;i++) {
		sj[i]=MX;
		sj[i]=gt(MX,i),f[i]=calc(i);
		for (int j=1;j<=M;j++) {cp[i][j]=(gcd(i,j)==1);}
	}
	scanf("%lld",&t);
	for (int i=1;i<=t;i++) {
		scanf("%lld%lld%lld",&a,&b,&c);
		ans=c%P;
		for (int i=1;i<=M;i++) {sja[i]=gt(a,i),sjb[i]=gt(b,i);}
		for (int i=1;i<=M;i++) {
			for (int j=1;j<=M;j++) {
				if (!cp[i][j]) {continue;}
				ll l=0,r=min(sja[i],sjb[j])/f[i];
				while (l<r) {
					ll mid=(l+r+1)>>1;
					if (qpow(mid*f[i],i)/i<=c/j) {l=mid;}
					else {r=mid-1;}
				}
				ans=(ans+l)%P;
				if (f[i]==1&&j/i<=c) {ans=(ans+P-1)%P;}
			}
		}
		printf("%lld\n",ans);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
 
